#ifndef _MY_REGEX_H
#define _MY_REGEX_H

#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <set>

using std::istream;
using std::vector;
using std::string;
using std::stack;
using std::set;

namespace MyRegex{

class DirectedGraph {
public:
	DirectedGraph(int vertices);
	~DirectedGraph();
	int V() const;
	int E() const;
	vector<int> adjacencies(int vertice) const;
	string toString() const;
	void addEdge(int v, int w);
private:
	DirectedGraph() = default;
	int vertices;
	int edges;
	vector<vector<int>> adj;
};

class DirectedGraphDFS {
public:
	DirectedGraphDFS(const DirectedGraph &graph, int vertice);
	DirectedGraphDFS(const DirectedGraph &graph, const set<int> &vertices);
	bool isMarked(int vertice) const;
private:
	vector<bool> marked;
	void dfs(const DirectedGraph &graph, int vertice);
};

class FiniteAutomate {
public:
	virtual bool recognize(const string &s) = 0;
};

class NFA: public FiniteAutomate{
public:
	NFA(const string &regex);
	virtual bool recognize(const string &s);
private:
	string regex;
	string::size_type regexMaxLength;
	DirectedGraph graph;
};

class Regex{
public:
	Regex(const string &regex);
	bool recognize(const string &s);
private:
	string regex;
};
};
#endif
